import math
import time

def is_prime_basic(n):
    """
    基础版素数判断函数
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # 检查从3到n-1的所有奇数
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    return True

def is_prime_optimized(n):
    """
    优化版素数判断函数
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # 只需要检查到sqrt(n)
    limit = int(math.sqrt(n)) + 1
    for i in range(3, limit, 2):
        if n % i == 0:
            return False
    return True

def print_primes(limit, prime_func, func_name):
    """
    输出素数并计时
    """
    print(f"\n=== 使用 {func_name} ===")
    start_time = time.time()
    
    count = 0
    primes = []
    
    for num in range(1, limit + 1):
        if prime_func(num):
            primes.append(num)
            count += 1
    
    # 按每行5个打印
    for i in range(0, len(primes), 5):
        line = primes[i:i+5]
        print(" ".join(f"{num:5d}" for num in line))
    
    end_time = time.time()
    elapsed = end_time - start_time
    
    print(f"\n在1~{limit}范围内找到 {count} 个素数")
    print(f"耗时: {elapsed:.4f} 秒")
    
    return elapsed

def main():
    limit = 20000
    
    # 测试两种方法的性能
    time_basic = print_primes(200, is_prime_basic, "基础方法")  # 先用小范围测试
    time_optimized = print_primes(200, is_prime_optimized, "优化方法")
    
    print(f"\n=== 性能比较 (范围1~200) ===")
    print(f"基础方法耗时: {time_basic:.4f} 秒")
    print(f"优化方法耗时: {time_optimized:.4f} 秒")
    print(f"优化后速度提升: {time_basic/time_optimized:.2f} 倍")
    
    # 最终用优化方法输出1~20000的素数
    print(f"\n=== 最终输出: 1~{limit}的素数 ===")
    print_primes(limit, is_prime_optimized, "优化方法")

if __name__ == "__main__":
    main()